//
// Created by Jisam on 14/09/2024 7:24 PM.
// Solution of  压岁钱
//#pragma GCC optimize(3)
#include <bits/stdc++.h>

using namespace std;
#define coutn(x) cout << (x) << "\n"
#define endl "\n"
#define PSI pair<string,int>
#define PII pair<int,int>
#define PDI pair<double,int>
#define PDD pair<double,double>
#define VVI vector<vector<int>>
#define VI vector<int>
#define VS vector<string>
#define PQLI priority_queue<int, vector<int>, less<int>>
#define PQGI priority_queue<int, vector<int>, greater<int>>
#define code_by_jisam ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
typedef long long i64;
typedef unsigned u32;
typedef unsigned long long u64;
typedef __int128 i128;
int dx[] = {-1, 1, 0, 0, 1, 1, -1, -1,};
int dy[] = {0, 0, -1, 1, 1, -1, -1, 1,};
const int inf = 998244353;
void solution() {
    string s; // 定义一个字符串变量s
    int k; // 定义一个整数变量k
    cin >> s >> k; // 从标准输入读取字符串s和整数k
    int n = (int) s.size(); // 获取字符串s的长度
    vector<vector<i64>> f(n, vector<i64>(k)); // 定义一个二维向量f，用于存储中间结果
    vector<vector<int>> vis(n, vector<int>(k)); // 定义一个二维向量vis，用于标记是否已经计算过某个状态

    // 定义一个递归函数dp，用于计算给定条件下的组合数量
    function<i64(int, int, int, int, const vector<int> &)> dp =
            [&](int dep, int up, int zero, int sum, const auto &a) {
                if (dep == -1) return (i64)((zero ^ 1) && sum == 0); // 如果已经处理完所有数字，检查是否满足条件
                if (up == 0 && zero == 0 && vis[dep][sum]) return f[dep][sum]; // 如果这个状态已经被计算过，直接返回结果
                int lim = a[dep]; // 获取当前数字的可能取值范围
                if (up == 0) lim = 9; // 如果是最后一个数字，取值范围是0到9
                i64 ret = 0; // 初始化返回值为0
                for (int i = 0; i <= lim; i++) { // 遍历所有可能的取值
                    // 递归调用dp函数，计算当前取值下的所有可能组合
                    ret = (ret + dp(dep - 1, up && i == lim, zero && i == 0, (sum + i) % k, a)) % inf;
                }
                if (up == 0 && zero == 0) vis[dep][sum] = 1, f[dep][sum] = ret; // 记录这个状态的结果
                return ret;
            };

    vector<int> a; // 定义一个向量a，用于存储字符串s中的每个数字
    for (char i: s) a.push_back(i - '0'); // 将字符串s中的每个字符转换为整数并存储到向量a中
    reverse(a.begin(), a.end()); // 反转向量a，因为我们从字符串的最后一个字符开始处理
    cout << dp(n - 1, 1, 1, 0, a) << '\n'; // 调用dp函数并输出结果
}

int main() {
    code_by_jisam;
    i64 T = 1;
    cin >> T;
    while (T--) {
        solution();
    }
    return 0;
}